package 每日一题;

import java.util.*;

/**
 * 830. 较大分组的位置
 */
public class Date0105 {
    public static void main(String[] args) {
        Date0105 test = new Date0105();
        System.out.println(test.largeGroupPositions("oocccccccccmmmmmmttt"));
    }
    /**
     * 自解：用指针i去遍历s，用map存储遍历结果
     * key为起始位置start value为重复的长度
     * 如果当前所指==后后一个 那么就 j= i+2 往后遍历判断是否继续相等
     *
     * 直到不相等 i=j;
     * 最终遍历map value》=3的输出[start，start+length+1]
     * ===问题：如果aba 就会以为三个连着等了
     * 修改：双指针  j= i+1
     * ===耗时 好空间
     * @param s
     * @return
     */
    public List<List<Integer>> largeGroupPositions(String s) {

        List<List<Integer>> rs = new ArrayList<>();
        Map<Integer,Integer> map = new TreeMap<>();
        if (s.length()<3){
            return rs;
        }
        int j=0;

        for (int i=0;i+2<s.length();i++){
            j=i+1;
            if(s.charAt(i) == s.charAt(j)){
                while (j<s.length() && s.charAt(j) == s.charAt(i) ){
                    j++;
                }
                if ((j-i)>=3){
                    map.put(i,j-1);
                }
                i=j-1;//因为for循环还要+1
            }else {
                continue;
            }
        }


        List<Integer> list =null;
        for (Map.Entry<Integer,Integer> d:map.entrySet()){
            list = new ArrayList<>();
            list.add(d.getKey());
            list.add(d.getValue());

            rs.add(list);
        }


        return rs;


    }

    /**
     * 题解方法：思路差不多 外面for循环的是j指针
     * i只是用来存储的
     * @param s
     * @return
     */
    public List<List<Integer>> largeGroupPositions1(String s) {
        List<List<Integer>> rs = new ArrayList<>();

        for (int i=0,j=0;j<=s.length();j++){
            //只有不相等时 i才移动
            if (j == s.length() || s.charAt(i) != s.charAt(j) ){
                if ((j-i)>=3){
                    rs.add(Arrays.asList(i,j-1));
                }
                i=j;
            }
        }

        return rs;
    }
}
